#include <bits/stdc++.h>
using namespace std;
 
// #define zerol
 
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout  << #x << " -> "; err(x); } while (0)
void err() { cout << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
 
 
//--------------------------------------------------------------------------------------------
 
LL p, n, m;
const int MAXN = 1e6+5;
 
int prime[MAXN], pcnt;
int minp[MAXN];
 
LL bin(LL a, LL b, LL p) {
    LL res = 1;
     
    for (a%=p; b; b>>=1, a=a*a%p)
        if (b & 1) res = res * a % p;
    return res;
}
 
 
 
void init() {
    for (int i=2; i<MAXN; ++i) {
        if (!minp[i]) {
            minp[i] = i;
            prime[pcnt++] = i;
        }
        for (int j=0; j<pcnt; ++j) {
            LL nextp = 1LL*i*prime[j];
            if (nextp >= MAXN) break;
            if (!minp[nextp])
                minp[nextp] = prime[j];
            if (i % prime[j]) break;
        }
    }
}
 
vector<LL> factor(LL n) {
    vector<LL> res;
    for (LL i=1; i*i<=n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            LL ano = n / i;
            if (ano != i)
                res.push_back(ano);
        }
    }
    sort(res.begin(), res.end());
    res.resize(unique(res.begin(), res.end()) - res.begin());
    return res;
}
 
typedef pair<LL, int> pLi;
 
vector<pLi> primeFactor(LL n) {
    vector<pLi> res;
    for (int i=0; i<pcnt; ++i) {
        if (n % prime[i] == 0) {
            int cnt = 0;
            for (; n % prime[i] == 0; n /= prime[i], ++cnt);
            res.push_back(make_pair(prime[i], cnt));
        }
    }
    if (n > 1) res.push_back(make_pair(n, 1));
    return res;
}
 
LL findsmallestx(LL p, LL phip) {
    vector<LL> v = factor(phip);
    for (LL x : v) {
        dbg(x, p);
        if (bin(10, x, p) == 1) return x;
    }
         
     
    return -1;
}
 
LL getphi(LL x) {
    vector<pLi> v = primeFactor(x);
    LL res = 1;
    for (const pLi p:v) {
        LL pr = p.first;
        int cnt = p.second;
        res *= (pr-1) * bin(pr, cnt-1, x);
    }
    return res;
}
 
namespace calc {
     
 
    LL n, m, p, k, blim, ans;
 
    LL dat[MAXN];
    vector<pLi> v;
 
    LL mutex(LL n) {
        LL res = 0;
        for (int i=1; i<blim; ++i) {
            res += n / dat[i];
        }
        // dbg(n, res);
        return n - res;
    }
 
    void dfs(int now, LL cur, LL minj, bool flag) {
        if (now == k) {
            if (!flag) ans += mutex(n / cur) * (m - minj + 1);
            return;
        }
         
        const pLi &info = v[now];
        LL p = info.first, lim = info.second;
        cur *= p;
 
        for (int i=1; cur<=n; cur*=p, ++i) {
            LL nextminj = max(minj, (lim + i-1) / i);
            dfs(now+1, cur, nextminj, flag && i >= lim);
        }
    }
 
    LL solve(LL _n, LL _m, LL _p) {
        n = _n;
        m = _m;
        p = _p;
        ans = 0;
 
        v = primeFactor(_p);
        dbg(p);
        k = v.size();
        blim = 1<<k;
        for (int i=1; i<blim; ++i) {
            dat[i] = -1;
            for (int j=0; j<k; ++j) {
                if ((i >> j) & 1) {
                    dat[i] *= -v[j].first;
                }
                 
            }
            // dbg(i, dat[i]);
        }
 
 
        dfs(0, 1, 1, 1);
        dbg(ans);
        ans += (n / p) * m;
        return ans;
    }
 
}
 
void solve() {
 
 
    scanf("%lld%lld%lld", &p, &n, &m);
 
 
    LL nextp = p;
    LL x = findsmallestx(p, getphi(nextp));
    // dbg(x);
    if (p == 2 || p == 5) {
        cout << 0 << endl;
        return;
    }
    if (p == 3) {
        printf("%lld\n", (n/3)*m);
        return;
    }
    // x = 5999999976;
    LL ans = calc::solve(n, m, x);
    cout << ans << endl;
}
 
 
int main(int argc, char const *argv[])
{
     
 
    init();
 
    int t;
    scanf("%d", &t);
    for (int kk=0; kk<t; ++kk)
        solve();
    /* code */
    return 0;
}